/**
 * 数独游戏核心算法模块
 * 包含数独生成、求解、验证等功能
 */

/**
 * 创建空的9x9数独网格
 */
function createEmptyGrid() {
  return Array(9).fill().map(() => Array(9).fill(0));
}

/**
 * 检查在指定位置放置数字是否有效
 */
function isValidMove(grid, row, col, num) {
  // 检查行
  for (let x = 0; x < 9; x++) {
    if (grid[row][x] === num) {
      return false;
    }
  }

  // 检查列
  for (let x = 0; x < 9; x++) {
    if (grid[x][col] === num) {
      return false;
    }
  }

  // 检查3x3宫格
  const startRow = row - row % 3;
  const startCol = col - col % 3;
  for (let i = 0; i < 3; i++) {
    for (let j = 0; j < 3; j++) {
      if (grid[i + startRow][j + startCol] === num) {
        return false;
      }
    }
  }

  return true;
}

/**
 * 使用回溯算法求解数独
 */
function solveSudoku(grid) {
  const newGrid = grid.map(row => [...row]);
  
  function solve() {
    for (let row = 0; row < 9; row++) {
      for (let col = 0; col < 9; col++) {
        if (newGrid[row][col] === 0) {
          for (let num = 1; num <= 9; num++) {
            if (isValidMove(newGrid, row, col, num)) {
              newGrid[row][col] = num;
              if (solve()) {
                return true;
              }
              newGrid[row][col] = 0;
            }
          }
          return false;
        }
      }
    }
    return true;
  }
  
  solve();
  return newGrid;
}

/**
 * 生成完整的数独解答
 */
function generateCompleteSudoku() {
  const grid = createEmptyGrid();
  
  // 填充对角线的3x3宫格
  fillDiagonal(grid);
  
  // 求解剩余部分
  const solvedGrid = solveSudoku(grid);
  
  return solvedGrid;
}

/**
 * 填充对角线的3x3宫格
 */
function fillDiagonal(grid) {
  for (let i = 0; i < 9; i += 3) {
    fillBox(grid, i, i);
  }
}

/**
 * 填充3x3宫格
 */
function fillBox(grid, row, col) {
  const nums = shuffleArray([1, 2, 3, 4, 5, 6, 7, 8, 9]);
  let index = 0;
  
  for (let i = 0; i < 3; i++) {
    for (let j = 0; j < 3; j++) {
      grid[row + i][col + j] = nums[index++];
    }
  }
}

/**
 * 打乱数组
 */
function shuffleArray(array) {
  const newArray = [...array];
  for (let i = newArray.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [newArray[i], newArray[j]] = [newArray[j], newArray[i]];
  }
  return newArray;
}

/**
 * 根据难度生成数独题目
 */
function generateSudokuPuzzle(difficulty = 'medium') {
  const solution = generateCompleteSudoku();
  const puzzle = solution.map(row => [...row]);
  
  // 根据难度确定要挖掉的格子数量
  const difficultySettings = {
    easy: { holes: 40, maxAttempts: 3 },
    medium: { holes: 50, maxAttempts: 5 },
    hard: { holes: 60, maxAttempts: 7 },
    expert: { holes: 70, maxAttempts: 10 }
  };
  
  const settings = difficultySettings[difficulty] || difficultySettings.medium;
  
  // 挖洞并确保唯一解
  let holes = 0;
  const attempts = [];
  
  while (holes < settings.holes && attempts.length < 1000) {
    const row = Math.floor(Math.random() * 9);
    const col = Math.floor(Math.random() * 9);
    
    if (puzzle[row][col] !== 0) {
      const backup = puzzle[row][col];
      puzzle[row][col] = 0;
      
      // 检查是否仍有唯一解
      if (hasUniqueSolution(puzzle, settings.maxAttempts)) {
        holes++;
      } else {
        puzzle[row][col] = backup;
      }
    }
    
    attempts.push({ row, col });
  }
  
  return {
    puzzle,
    solution,
    difficulty,
    holes
  };
}

/**
 * 检查数独是否有唯一解
 */
function hasUniqueSolution(grid, maxAttempts = 5) {
  let solutionCount = 0;
  const testGrid = grid.map(row => [...row]);
  
  function countSolutions(attempts = 0) {
    if (attempts > maxAttempts || solutionCount > 1) {
      return;
    }
    
    for (let row = 0; row < 9; row++) {
      for (let col = 0; col < 9; col++) {
        if (testGrid[row][col] === 0) {
          for (let num = 1; num <= 9; num++) {
            if (isValidMove(testGrid, row, col, num)) {
              testGrid[row][col] = num;
              countSolutions(attempts + 1);
              testGrid[row][col] = 0;
              
              if (solutionCount > 1) {
                return;
              }
            }
          }
          return;
        }
      }
    }
    solutionCount++;
  }
  
  countSolutions();
  return solutionCount === 1;
}

/**
 * 验证完整的数独是否正确
 */
function isValidSudoku(grid) {
  // 检查是否填满
  for (let row = 0; row < 9; row++) {
    for (let col = 0; col < 9; col++) {
      if (grid[row][col] === 0) {
        return false;
      }
    }
  }
  
  // 检查每行、每列、每个3x3宫格
  for (let i = 0; i < 9; i++) {
    if (!isValidUnit(getRow(grid, i)) || 
        !isValidUnit(getColumn(grid, i)) || 
        !isValidUnit(getBox(grid, i))) {
      return false;
    }
  }
  
  return true;
}

/**
 * 获取指定行
 */
function getRow(grid, row) {
  return grid[row];
}

/**
 * 获取指定列
 */
function getColumn(grid, col) {
  return grid.map(row => row[col]);
}

/**
 * 获取指定3x3宫格
 */
function getBox(grid, boxIndex) {
  const box = [];
  const startRow = Math.floor(boxIndex / 3) * 3;
  const startCol = (boxIndex % 3) * 3;
  
  for (let i = 0; i < 3; i++) {
    for (let j = 0; j < 3; j++) {
      box.push(grid[startRow + i][startCol + j]);
    }
  }
  
  return box;
}

/**
 * 验证一个单元（行、列或宫格）是否有效
 */
function isValidUnit(unit) {
  const seen = new Set();
  for (const num of unit) {
    if (num !== 0) {
      if (seen.has(num)) {
        return false;
      }
      seen.add(num);
    }
  }
  return true;
}

/**
 * 获取数独提示
 */
function getSudokuHint(grid, solution, row, col) {
  if (grid[row][col] !== 0) {
    return null; // 该位置已有数字
  }
  
  if (!solution || solution.length !== 9) {
    return null; // 无有效解答
  }
  
  return solution[row][col];
}

/**
 * 获取指定位置的可能数字
 */
function getPossibleNumbers(grid, row, col) {
  if (grid[row][col] !== 0) {
    return [];
  }
  
  const possible = [];
  for (let num = 1; num <= 9; num++) {
    if (isValidMove(grid, row, col, num)) {
      possible.push(num);
    }
  }
  
  return possible;
}

module.exports = {
  createEmptyGrid,
  isValidMove,
  solveSudoku,
  generateCompleteSudoku,
  generateSudokuPuzzle,
  isValidSudoku,
  getSudokuHint,
  getPossibleNumbers,
  hasUniqueSolution
};